1. Technical Field
The present invention relates in general to an improved method of error detection, and, in particular, to an improved method of discovering errors in a logical function. Still more particularly, the present invention relates to an improved method for discovering errors in shift, rotate, and sign extension functions.
2. Description of the Related Art
With the increasing penetration of microprocessor-based systems into every facet of human activity, demands have increased on the microprocessor development and production community to produce systems that are free from data corruption. Microprocessors have become involved in the performance of a vast array of critical functions, and the involvement of microprocessors in the important tasks of daily life has heightened the expectation of reliability of calculative results. Whether the impact of errors would be measured in human lives or in mere dollars and cents, consumers of microprocessors have lost tolerance for error-prone results. Consumers will not tolerate, by way of example, miscalculations on the floor of the stock exchange, in the medical devices that support human life, or in the computers that control their automobiles. All of these activities represent areas where the need for reliable microprocessor results has risen to a mission-critical concern.
In applications where reliability is considered paramount, designers commonly employ duplicate logic to perform calculations twice (in parallel) and compare the results of the duplicated function. This allows a microprocessor system to detect circuit failure, and to prevent an internal error from fouling the results of a calculation. As can be easily imagined, there is an inherent inefficiency in duplication of a function. Simply stated, the duplication of a function doubles the circuitry necessary to perform a given calculation, resulting in increased design complexity and chip size. Fabrication costs, design time, power consumption, and the potential for errors all increase with the amount of circuitry on a chip.
The complexity, power consumption, and cost associated with conventional error checking techniques have motivated the use of cheaper alternatives. For example, one alternative method of checking for circuit failure and mathematical calculation errors, without having to duplicate logic, is moduli or residue checking. The modulo function has proven useful for streamlining error-checking operations, but its applicability conventionally is limited by the methods that are conventionally used to calculate it.
The modulo operator (mod) returns the remainder after integer division of its first argument by its second. If a is any integer and n is a positive integer, a mod n is the expression for the remainder in {0, . . . , n−1} that occurs if a is divided by n. For instance, 23 mod 12=11. As another example, a mod 12 is performed to convert the time from a 24-hour format to a 12-hour format.
In practice, x mod y can be calculated in terms of other functions. Differences arise according to the scope of the variables, which in common implementations is broader than in the definition just given. In terms of the floor function floor(z), the greatest integer less than or equal to z: x mod y=x−y*floor(x/y). In terms of truncation to the integer part (known as remain( ) on several calculators and always positive; performed by C's built-in % operator): x mod y=x−y*iPart(x/y). In the case of floor, a negative divisor results in a negative modulus (for example, under this definition, 1 mod−2=−1). The resulting function is what is known as mod( ) on calculators and is implemented in some high-level languages, including Perl. Perl also uses the % operator to indicate a modulus operation, alluding to the / division operator. Both definitions allow for x and y to be typed as integers or rational numbers. Each of these definitions requires the preservation of the operands of the original function to be checked.
As a practical matter, modulo functions have proven useful in error checking without function duplication for functions whose operands are not discarded during calculation. However, conventional modulo/residue checking is available only where both the input of a function and the result of a function are available after the function is complete. Accordingly, conventional modulo/residue checking cannot be used to check rotate, sign extend, or shift functions, because their operands are discarded or altered in the course of the underlying operation. Storage of the operands of a function for later calculation of a modulo check would involve a waste of resources in terms of complexity, power consumption, and cost. Thus, storage of operands would cause problems unacceptably similar to the problems presented by duplicating a function and comparing the two results.
What is needed is a method for detecting errors in a processor that performs shift, rotate, and sign extension functions, with that method using the modulo function to detect errors.